#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int QuickSortPass(int *arr, int start, int end)
{
    if(start == end) return 0;
    int k = rand() % (end - start + 1);
    k = start + k;
    swap(&arr[k], &arr[end]);
    int small = start - 1;
    for(int index = start; index < end; ++index)
    {
        if(arr[index] <= arr[end])
        {
            small++;
            swap(&arr[small], &arr[index]);
        }
    }
    small++;
    swap(&arr[small], &arr[end]);
    return small;
}

void QuickSort(int *arr, int length)
{
    if(arr == NULL || length == 0) return;

    int k = QuickSortPass(arr, 0, length - 1);
    QuickSort(arr, k); // 左序列
    QuickSort(arr + k + 1, length - k - 1); // 右序列
}

void Print(int* arr, int length)
{
    for(int i = 0; i < length; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main()
{
    // 普通序列
    int arr[] = {1,3,2};
    QuickSort(arr, 3);
    Print(arr, 3);
    // 只增序列
    int arr2[] = {1, 2, 3};
    QuickSort(arr2, 3);
    Print(arr2, 3);
    // 只减序列
    int arr3[] = {3, 2, 1};
    QuickSort(arr3, 3);
    Print(arr3, 3);
    // 不增不减
    int arr4[] = {3, 3, 3};
    QuickSort(arr4, 3);
    Print(arr4, 3);
    // 一个元素
    int arr5[] = {1};
    QuickSort(arr5, 1);
    Print(arr5, 1);
    // 2个元素
    int arr6[] = {1,2};
    QuickSort(arr6, 2);
    Print(arr6, 2);
    // 空指针
    QuickSort(NULL, 0);

    return 0;
}